#include <iostream>
#include <vector>
#include <queue>
#include "utils.h"
using namespace std;

class Solution {
public:
    ListNode* get_mid(ListNode *beg, ListNode *end)
    {
        int len = 0;
        ListNode *p = beg;
        while(p!=end) {
            p = p->next;
            len++;
        }
        len >>= 1;
        while(len--) {
            beg = beg->next;
        }
        return beg;
    }

    TreeNode *sortedListToBST(ListNode *head, ListNode *tail)
    {
        if (head == tail) return NULL;

        ListNode *mid = get_mid(head, tail);

        TreeNode *root = new TreeNode(mid->val);
        root->left = sortedListToBST(head, mid);
        root->right = sortedListToBST(mid->next, tail);
        return root;
    }

    TreeNode *sortedListToBST(ListNode *head) {
        return sortedListToBST(head, NULL);
    }
};

int main(int argc, char *argv[])
{
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8};
    ListNode *head = make_list(a, sizeof(a)/sizeof(int));
    print_list(head);

    Solution ss;
    TreeNode *root = ss.sortedListToBST(head);
    print_vector(levelOrder(root));
    return 0;
}
